/*
 * GaliliSeiferas.cpp
 *
 *  Created on: 29-08-2013
 *      Author: Krzychu
 */

#include "GaliliSeiferas.h"

#include "Config.h"

#include <stdio.h>
#include <string.h>

GaliliSeiferas::GaliliSeiferas()
{

}

GaliliSeiferas::~GaliliSeiferas()
{

}

std::string GaliliSeiferas::getName()
{
	return "Galil Seiferas";
}

searchResult result;
const char *x, *y;
int k, m, n, p, p1, p2, q, q1, q2, s;

void search()
{
	while (p <= n - m)
	{
		result.iterationsTaken++;
		while (p + s + q < n && x[s + q] == y[p + s + q])
			++q;
		if (q == m - s && memcmp(x, y + p, s + 1) == 0)
		{
			result.positionsFound.push_back(p);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return;
			}
		}
		if (q == p1 + q1)
		{
			p += p1;
			q -= p1;
		}
		else
		{
			p += (q / k + 1);
			q = 0;
		}
	}
}

void GaliliSeiferas::parse()
{
	while (1)
	{
		while (x[s + q1] == x[s + p1 + q1])
			++q1;
		while (p1 + q1 >= k * p1)
		{
			s += p1;
			q1 -= p1;
		}
		p1 += (q1 / k + 1);
		q1 = 0;
		if (p1 >= p2)
			break;
	}
	newP1();
}

void GaliliSeiferas::newP2()
{
	while (x[s + q2] == x[s + p2 + q2] && p2 + q2 < k * p2)
		++q2;
	if (p2 + q2 == k * p2)
		parse();
	else if (s + p2 + q2 == m)
		search();
	else
	{
		if (q2 == p1 + q1)
		{
			p2 += p1;
			q2 -= p1;
		}
		else
		{
			p2 += (q2 / k + 1);
			q2 = 0;
		}
		newP2();
	}
}

void GaliliSeiferas::newP1()
{
	while (x[s + q1] == x[s + p1 + q1])
		++q1;
	if (p1 + q1 >= k * p1)
	{
		p2 = q1;
		q2 = 0;
		newP2();
	}
	else
	{
		if (s + p1 + q1 == m)
		{
			search();
		}
		else
		{
			p1 += (q1 / k + 1);
			q1 = 0;
			newP1();
		}
	}
}

searchResult GaliliSeiferas::execute(std::string text, std::string pattern)
{
	result.iterationsTaken = 0;

	x = pattern.c_str();
	y = text.c_str();

	k = 4;
	p = q = s = q1 = p2 = q2 = 0;
	p1 = 1;
	newP1();

	return result;
}
